package DynamicProgramming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _368_LargestDivisibleSubset {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        if(nums.length==0) return new ArrayList<>();
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        int max = 0;
        int index = 0;
        for (int i = 0; i < len; i++) {
            List<Integer> temp = new ArrayList<>();
            temp.add(nums[i]);
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    if (dp[j] + 1 > dp[i]) {
                        temp = new ArrayList<>();
                        temp.addAll(res.get(j));
                        temp.add(nums[i]);
                        dp[i] = dp[j] + 1;
                    }
                    if (dp[i] > max) {
                        max = dp[i];
                        index = i;
                    }

                }
            }
            res.add(temp);
        }
        System.out.println(res.toString());
        return res.get(index);
    }
}
